class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        if(prices.size() < 1)
            return 0;

        int minprices = prices[0];
        int profit = 0;

        for(int i = 0; i < prices.size() - 1; i++)
        {

            minprices = min(prices[i + 1], minprices);
            profit = max(prices[i + 1] - minprices, profit);
    
        }

        return profit;
    }
};

//动态规划，第i天收益最大值 = max（前i-1天收益最大值，第i天价格-前i-1天所记录的最小值）